#include <iostream>

// 宏定义  不加 分号
#define maxV 10

// 判断 拓扑排序是否唯一
typedef struct
{
    int numVertices, numEdges; // 顶点 边数
    char verticesList[maxV];   // 顶点列表

    int edge[maxV][maxV]; // 邻接矩阵
} MGraph;

// 拓扑排序 是否唯一  返回 1 或者0

// ################  思路 同时存在 多个入度为0的节点 则不唯一 ############################################################
int quely(MGraph &G)
{
    int index = 0;                  // 当前入度为0的节点
    int inDegree[maxV] = {0};       // 入度
    int outedNodeIndex[maxV] = {0}; // 出队列的节点
    // 初始化节点入度列表
    for (int i = 0; i < G.numVertices; i++)
    {
        for (int j = 0; j < G.numVertices; j++)
        {
            if (G.edge[i][j] != 0)
            {
                inDegree[j]++;
            }
        }
    }
    // 一轮循环 检测是否有环 是否 多个 入度为0的节点 若只有 一个 入度为0的节点 出队列 跟新 入度表
    for (int k = 0; k < G.numVertices; k++)
    {
        int numZeroInDegree = 0;
        for (int i = 0; i < G.numVertices; i++)
        {
            if (!outedNodeIndex[i] && inDegree[i] == 0)
            {
                numZeroInDegree++;
            }
        }

        // 如果没有入度为 0 的点，说明有环
        if (numZeroInDegree == 0)
            return 0;

        // 如果入度为 0 的点多于 1 个，则拓扑序列不唯一
        if (numZeroInDegree > 1)
            return 0;

        // 找到 入度为0的节点 出队列
        for (int i = 0; i < G.numVertices; i++)
        {
            if (!outedNodeIndex[i] && inDegree[i] == 0) // 此节点 未出队列 并且 入度为0
            {
                outedNodeIndex[i] = 1;
                // 更新入度
                for (int j = 0; j < G.numVertices; j++)
                {
                    if (G.edge[i][j] != 0)
                    {
                        inDegree[j]--; // 该节点出队后，它指向的节点入度 -1
                    }
                }
                break; // 由于拓扑序列唯一，每次只会出队 1 个节点
            }
        }
    }

    // 检查是否有 入度为0的节点
    // 检查 多个入度为0的节点
    // 找到 入度为0的节点 出队列
    // 出队列 就是跟新 入度表

    return 1;
}

int main()
{
    MGraph G;
    G.numVertices = 3; // 顶点数
    G.numEdges = 2;    // 边数

    // 初始化顶点列表
    G.verticesList[0] = 'A';
    G.verticesList[1] = 'B';
    G.verticesList[2] = 'C';

    // 初始化邻接矩阵（全部设为0）
    for (int i = 0; i < maxV; i++)
        for (int j = 0; j < maxV; j++)
            G.edge[i][j] = 0;

    // **手动添加边**
    G.edge[0][1] = 1; // A → B
    G.edge[0][2] = 1; // A → c

    printf("is uiqueSort %d\n", quely(G));

    return 0;
}
